#include <vector>
#include <iostream>

using namespace std;

int makingChange(int amount, int limit, vector<int> coins) {
  // 1. 每下降一层，coins 中的硬币面额就要少一个
  // 2. 在同一层，接下来要找的钱，和可用的硬币数要随着选择的硬币变化
  int result = 0;
  int coin = coins.back();
  coins.pop_back();

  if (coins.size() == 0) {
    // coin 就是最后一个可以用于找钱的面额
    if (amount / coin <= limit) {
      return 1;
    }
  }
  else {
    // 拿走了一个 coin 用于分配之后，coins 数组中仍旧有其它硬币。
    // 用 coin 找 amount 最多能用多少个: amount / coin
    for (int i = 0; i <= amount / coin; ++i) {
      // i = 0
      // makingChange(amount - 0 * coin, limit - 0, coins) +
      // i = 1
      // makingChange(amount - 1 * coin, limit - 1, coins) +
      // i = 2
      // makingChange(amount - 2 * coin, limit - 2, coins)
      result += makingChange(amount - i * coin, limit - i, coins);
    }
  }

  return result;
}

int main(int argc, char const *argv[])
{
  /* code */
  cout << makingChange(1000, 15, {10, 50, 100, 500}) << endl;
  return 0;
}


